Leftover Hash Lemma

释义 Definition

“Leftover Hash Lemma（剩余哈希引理）”是密码学与随机性提取（randomness extraction）中的一个核心结果：如果一个随机变量具有足够的最小熵（min-entropy），那么用通用哈希函数族（universal hashing）对其进行哈希，可以把它“提取/压缩”为一段与均匀随机几乎不可区分的比特串（在统计距离意义下接近均匀），常用于隐私放大与密钥生成。

发音 Pronunciation (IPA)

/ˈlɛftˌoʊvər hæʃ ˈlɛmə/

例句 Examples

We apply the leftover hash lemma to extract a nearly uniform key.
我们应用剩余哈希引理来提取一把近似均匀随机的密钥。

Given a source with high min-entropy, the leftover hash lemma shows that universal hashing yields an output statistically close to uniform, even when an adversary has partial information.
对于具有较高最小熵的来源，剩余哈希引理表明：即使攻击者掌握部分信息，使用通用哈希仍能得到在统计意义上接近均匀分布的输出。

词源 Etymology

该术语出自密码学语境：leftover强调“提取后剩下的随机性/不确定性”，hash指哈希函数（尤其是通用哈希），lemma是数学中“引理”的常用称呼。整体含义可理解为：用哈希把来源中的“剩余随机性”转化为近似均匀的输出。该结果与隐私放大（privacy amplification）思想密切相关，后来在现代密码学教材中固定为“Leftover Hash Lemma”这一专名。

相关词 Related Words

• Universal Hashing
• Hash Function
• Randomness Extractor
• Privacy Amplification
• Min-Entropy
• Statistical Distance
• Seed
• Pseudorandomness

文献与著作 Literary / Notable Works

• Introduction to Modern Cryptography（Katz & Lindell）——在随机性提取、隐私放大与通用哈希相关章节中讲解并使用该引理。
• Foundations of Cryptography（Oded Goldreich）——在伪随机性与提取器等理论框架下讨论该引理及其变体。
• Complexity and Cryptography: An Introduction（John Talbot & Dominic Welsh）——在密码学基础与随机性相关内容中引用该结果。
• 经典论文脉络中与该引理紧密相关的“隐私放大”研究（如 Bennett、Brassard 等人的工作）常被现代表述联系到 Leftover Hash Lemma。